"""
现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。
您有一个单词列表（从词典中获得的），该单词列表内的单词已经按这门新语言的字母顺序进行了排序。
需要根据这个输入的列表，还原出此语言中已知的字母顺序。


输入:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
输出: "wertf"

"""
from mode import *


class Solution:
    def alienOrder(self, words):
        hasAlpha = [0 for _ in range(26)]
        count = 0
        size = len(words)
        for word in words:
            for char in word:
                hasAlpha[ord(char) - ord('a')] = 1

        for i in hasAlpha:
            if i != 0:
                count += 1

        hashMap = {}
        indegree = [0 for _ in range(26)]
        for i in range(size - 1):
            curStr = words[i]
            nextStr = words[i + 1]

            minSize = min(len(curStr), len(nextStr))
            for j in range(minSize):
                if curStr[j] != nextStr[j]:
                    if curStr[j] not in hashMap:
                        hashMap[curStr[j]] = []
                    hashMap[curStr[j]].append(nextStr[j])
                    indegree[ord(nextStr[j]) - ord('a')] += 1
                    # continue

        deque = collections.deque()
        for i in range(26):
            if indegree[i] == 0 and hasAlpha[i]:
                deque.append(chr(i + ord('a')))

        hasHad = [0 for _ in range(26)]

        res = []
        while deque:
            size = len(deque)
            for i in range(size):
                curChar = deque.popleft()
                res.append(curChar)
                hasHad[ord(curChar) - ord('a')] = 1

                if hashMap.get(curChar):
                    for nextChar in hashMap[curChar]:
                        indegree[ord(nextChar) - ord('a')] -= 1

                        if indegree[ord(nextChar) - ord('a')] == 0 and hasHad[ord(nextChar) - ord('a')] == 0:
                            hasHad[ord(nextChar) - ord('a')] = 1
                            deque.append(nextChar)

        return '' if len(res) != count else ''.join(res)


if __name__ == "__main__":
    A = Solution()
    print(A.alienOrder(["wrt", "wrf", "er", "ett", "rftt"]))
